/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/topological-sorting
   @Language: C++
   @Datetime: 17-03-29 17:51
   */
/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
public:
	/**
	 * @param graph: A list of Directed graph node
	 * @return: Any topological order for the given graph.
	 * Tip: BFS (Using Queue)
	 *   1: statistics all node' in degrees
	 *   2: add all 0 in degree nodes to queue
	 *   3: traversal queue, each q add to topsort,
	 *      and update q's neighbours' in degree,
	 *      and add new 0 in degree nodes to queue.
	 *   4: untill queue is empty.
	 *   if not all nodes are in topsort, means the graph has circle
	 */
	vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
		// write your code here
		int N = graph.size();
		unordered_map<DirectedGraphNode*,int> indes;    // indegree
		for(int i=0; i<N; indes[graph[i++]]=0);
		for(int i=0; i<N; ++i)
			for(int j=0; j<graph[i]->neighbors.size(); ++j)
				++indes[graph[i]->neighbors[j]];
		// find nodes whose in degree is 0
		queue<DirectedGraphNode*> que;
		for(const auto &de:indes)
			if (de.second==0) que.push(de.first);
		vector<DirectedGraphNode*> topsort;
		for(; que.size(); --N, que.pop()){  // que.size()>1 has not 1 topsort
			DirectedGraphNode *q = que.front();
			topsort.push_back(q);
			for(int i=0; i<q->neighbors.size(); ++i){
				--indes[q->neighbors[i]];// delete edge(in degree)
				if (indes[q->neighbors[i]]==0) que.push(q->neighbors[i]);
			}
		}
		if (N>0) ; // graph has circle, no topsort
		return topsort;
	}
};
